package notes.java.sort;

/**
 * 插入排序
 * 1、从第2个数开始，和它前面第1个数比较，小就移到前面
 * 2、接着第3个数，和前面第2个数比较，小就移到前面，再和第1个数比较，小就移到前面
 * 3、依次直到第n个数，分别和第n-1,n-2...1比较，小就移到前面
 *
 */
public class S3_InsertSort {

	public static void main(String[] args) {
		
		// 定义一个数组
		int[] num = { 5, 9, 4, 8, 2, 1, 0, 7, 3, 6 };
		
		// 从第2个数开始
		for(int i=1; i<num.length; i++) {
			
			// 分别和前面的数比较，小就移到前面
			for(int j=i; j>0; j--) {
				if(num[j] < num[j-1]) {
					int temp = num[j];
					num[j] = num[j-1];
					num[j-1] = temp;
				}
			}
			
			print(num, i);
		}
		
	}
	
	/** 打印输出*/
	private static void print(int[] num, int n) {
		// 输出
		for (int i = 0; i < num.length; i++) {
			if(i == n) {
				System.out.print("↑" + num[i] + " ");
			} else {
				System.out.print(num[i] + " ");
			}
		}
		System.out.println();
	}

}
